home *** CD-ROM | disk | FTP | other *** search
/ Windows Expert / Windows Expert.iso / windownt / wvnsrc75.zip / SHELLSOR.C < prev    next >
C/C++ Source or Header  |  1993-02-03  |  3KB  |  76 lines
  1.  
  2. /* Shellsort is a variation on Insertion Sort that is virtually unbeatable
  3.  * on small data sets.  Insertion Sort is slow because it only exchanges
  4.  * adjacent elements.  Shellsort circumvents this by allowing the exchange
  5.  * of elements that are farther apart.  It works by first performing Insertion
  6.  * Sort on subsets of the data.  For example, Shellsort might first sort
  7.  * the set of elements 1, 6, 11, 16... relative to each other--the effect
  8.  * is that the elements in that subset are moved much closer to their final
  9.  * positions.  At first the sets are wide-spread, perhaps every fortieth
  10.  * element.  Then it repeats using a tighter set, perhaps every fourteenth
  11.  * element, then every fourth element.  Each of these passes is much cheaper
  12.  * than a traditional Insertion Sort pass.  The effect of the passes is that
  13.  * the data set is mutated to be in "almost sorted" order.  The final insertion
  14.  * sort pass can then go very quickly because insertion sort does very well on
  15.  * almost sorted data.  In other words, at first the elements take large leaps
  16.  * to the general location they belong and successively smaller steps move the
  17.  * element to its precise place. I call this algorithm "inscrutable sort"
  18.  * because even after having coded the algorithm, I still have trouble
  19.  * following the animation.  No one has been able to analyze this algorithm
  20.  * rigorously; the functional form of the running time is conjectured to be
  21.  * O(N^1.25).  Shellsort may be a bit mysterious, but it is an good general
  22.  * purpose sort since it has excellent performance and the code you must write
  23.  * is only slightly more complex than Insertion Sort.
  24.  *
  25.  * Author: Julie Zelenski, NeXT Developer Support
  26.  * You may freely copy, distribute and reuse the code in this example.
  27.  * NeXT disclaims any warranty of any kind, expressed or implied, as to
  28.  * its fitness for any particular use.      qsort
  29.  */
  30.  
  31. #include <stdio.h>
  32. #include <string.h>
  33.  
  34. #define memSwap(a,b,unused) tmp = *(char  *  *)(a); \
  35.   *(char  *  *)(a) = *(char  *  *)(b); *(char  *  *)(b) = tmp;
  36.  
  37.  
  38. void
  39. ShellSort (base, nElements, width, compare)
  40.      void *base;
  41.      size_t nElements;
  42.      size_t width;
  43.      int (* compare) (void const * elem1, void const * elem2);
  44. {
  45. #define STRIDE_FACTOR 3
  46.   int c, d, stride;
  47.   char *tmp;
  48.   int found;
  49.  
  50.   stride = 1;
  51.   while (stride <= nElements)
  52.     stride = stride * STRIDE_FACTOR + 1;
  53.  
  54.   while (stride > (STRIDE_FACTOR - 1))
  55.     {
  56.       stride = stride / STRIDE_FACTOR;
  57.       for (c = stride; c < nElements; c++)
  58.     {
  59.       found = 0;
  60.       d = c - stride;
  61.       while ((d >= 0) && !found)
  62.         {
  63.           if (compare ((char *) base + (d + stride) * width, (char *) base + d * width) < 0)
  64.         {
  65.           memSwap ((char  *) base + (d + stride) * width, (char  *) base + d * width, width);
  66.           d -= stride;
  67.         }
  68.           else
  69.         {
  70.           found = 1;
  71.         }
  72.         }
  73.     }
  74.     }
  75. }
  76.